#define  _CRT_SECURE_NO_WARNINGS 1	
#include<stdio.h>
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] > a[end])
			return end;
		else
			return begin;
	}
	else
	{
		if (a[begin] > a[end])
			return begin;
		else if (a[mid] > a[end])
			return end;
		else
			return mid;
	}
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);

	int left = begin;
	int right = end;

	int cur = begin + 1;
	int key = a[begin];

	while (cur <= end)
	{
		if (a[cur] < key)
		{
			swap(&a[cur], &a[begin]);
			begin++;
			cur++;
		}
		else if (a[cur] > key)
		{
			swap(&a[cur], &a[end]);
			end--;
		}
		else
		{
			cur++;
		}
	}
	QuickSort(a, left, begin - 1);
	QuickSort(a, end + 1, right);
}

int main()
{

	int a[] = { 6,1,2,6,6,8,6 };
	QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
		printf("%d ", a[i]);
	return 0;
}